package 中等.动态规划.数组区间;

/**
 * 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
 * <p>
 * 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
 * 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
 * <p>
 * 子数组 是数组中的一个连续序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/arithmetic-slices
 */
public class 等差数列划分_413 {

    public static void main(String[] args) {

        int[] nums = {1, 3, 5, 8, 8, 8, 8};
        System.out.println(numberOfArithmeticSlices(nums));

    }

    /**
     * 等差数列判断：
     * nums[i]-nums[i-1]=nums[i-1]-nums[i-2]
     * 子问题：
     * 以i元素结尾的等差数列有多少个=以i-1元素结尾的等差数列个数+1
     * 例如：
     * nums{01238888}
     * 以索引2结尾的等差数列：
     * {012}
     * 以索引3结尾等差数列：
     * {0123}  索引2结尾的等差数列个数+
     * {123}   新增1
     * 以索引4,5结尾的等差数列个数=0
     * 以索引6结尾的等差数列个数
     * {888}
     * 以索引7结尾的等差数列个数
     * {8888}  索引6结尾的等差数列个数+
     * {888}   新增1
     * <p>
     * dp{00120012}
     * <p>
     * 求的原数组的全部等差子数列，dp求和=结果
     *
     * @param nums
     * @return
     */
    public static int numberOfArithmeticSlices(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int[] dp = new int[nums.length];
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int count = 0;
        for (int i : dp) {
            count = count + i;
        }
        return count;
    }

}
